public class Heap{
		
		public int[] array;
		public int count;
		public int capacity;
		public int heapType;
		
		//Creating Heap
		
		public Heap(int capacity, int heapType, int[] array)
		{
			this.heapType = heapType;
			this.capacity = capacity;
			this.count = array.length;
			this.array = new int[capacity];
			this.array = array;
		}

		//Parent of Node(i-1/2 th location)

		public int parent(int i)
		{
			if(i <= 0 || i > this.count)
				return -1;
			return ((i-1)/2);
		}

		//Left child is at 2i+1th location

		public int leftChild(int i)
		{
			int left = 2*i+1;
			if(left > this.count)
				return -1;
			return left;
		}
		public int rightChild(int i)
		{
			int right = 2*i+2;
			if(right > this.count)
				return -1;
			return right;
		}
		public int getMaximum()
		{
			if(this.count == 0)
				return -1;
			return(this.array[0]);
		}


	public static void main(String[] args)
	 {	
		int[] arr = {1,15,2,16,17,4,3};
		Heap newHeap = new Heap(7,0,arr);
		System.out.println(newHeap.getMaximum());
		System.out.println(newHeap.parent(6));
	}


	//heapifying at element i. After insertion, percolating down. After insertion, find the element where there is a problem. 
	//Find max of the children and swap the current element with that. contiunue to percolate down.
	public void percolateDown(int i)
	{
		int l, r, max, temp;
		l = leftChild(i);
		r = rightChild(i);
		//Find max
		if(l != -1 && this.array[l] > this.array[i])
			max = l;
		else
			max = i;
		if(r != -1 && this.array[r] > this.array[max])
			max = r;

		//swap
		if(max != i)
		{
			temp = this.array[i];
			this.array[i] = array[max];
			this.array[max] = temp;
		}

		percolateDown(max);
	}


	int DeleteMax()
	{
		if(this.count == 0)
			return -1;
		int data = this.array[0];
		this.array[0] = this.array[count-1];
		this.count--;
		percolateDown(0);
		return data;
	}

	int insert(int data)
	{
		if(this.count == this.capacity)
			resizeHeap();
		this.count++;
		i = this.count-1;
		while(i>=0 && this.data > this.array[(i-1)/2])
		{
			this.array[i] = this.array[(i-1)/2];
			i = (i-1)/2;
		}
		this.array[i] = data;
	}




}